/*
 *  Shell sort(h-sort, improved insertion sort indeed)
 */
package algs4.sort;

public class Shell
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        int n = a.length;
        int h = 1;

        // h series
        while (h < n) h = h * 3 + 1;

        h /= 3;

        while (h > 0) {
            for (int i = h; i < n; i++) {
                int        j = i;
                Comparable v = a[i];

                for (; j >= h && v.compareTo(a[j-h]) < 0; j -= h)
                    a[j] = a[j-h];

                a[j] = v;
            }

            h /= 3;
        }
    }

    public static void sort(Comparable[] a, int st, int ed) {
        int n = ed - st + 1;
        int h = 1;

        // h series
        while (h < n) h = h * 3 + 1;

        h /= 3;

        while (h > 0) {
            for (int i = st + h; i <= ed; i++) {
                int        j = i;
                Comparable v = a[i];

                for (; j >= st + h && v.compareTo(a[j-h]) < 0; j -= h)
                    a[j] = a[j-h];

                a[j] = v;
            }

            h /= 3;
        }
    }
}
